#include<iostream>
#include<algorithm>
using namespace std;
const int N = 510, M = N * N / 2;
int n, price;
int p[N];
int ans;
int cnt, num, sum;
int find(int x)
{
	if (x != p[x])p[x] = find(p[x]);
	return p[x];
}
struct node
{
	int a, b, w;
}S[M];
int cmp(node a, node b)
{
	return a.w < b.w;
}
void kruskal()
{
	for (int i = 1; i <= n; i++)p[i] = i;
	for (int i = 1; i <= cnt - num; i++) {
		int a = S[i].a;
		int b = S[i].b;
		a = find(a);
		b = find(b);
		if (a != b) {
			ans += S[i].w;
			p[a] = b;
			sum++;
		}
	}
}
int main()
{
	cin >> price >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int w;
			cin >> w;
			if (i >= j || !w)continue;
			S[++cnt] = { i,j,w };
			if (w > price)num++;
		}
	}
	//cout << "cnt==" << cnt << endl;
	sort(S + 1, S + cnt + 1, cmp);
	kruskal();
	//cout << "ans==" << ans << endl;
	if (sum == n - 1)cout << ans + price << endl;
	else cout << ans + (n - sum) * price << endl;
	return 0;
}